package com.test.daily.leetcode.y2022.m07.day0719.v01;

import java.util.ArrayList;
import java.util.List;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/19 上午 08:53
 * @version: 1.0
 */
public class Solution {
    public static class Node {
        public Node left;
        public Node right;
        public int value;

        public Node(int value) {
            this.value = value;
        }
    }

    public int max(Node head) {
        int max = 0;
        max = Math.max(max, maxSubBST(head));
        return Math.max(max, Math.max(maxSubBST(head.left), maxSubBST(head.right)));
    }

    public int maxSubBST(Node head) {
        List<Node> list = new ArrayList<>();
        in(head, list);
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i).value >= list.get(i - 1).value) {
                return 0;
            }
        }
        return list.size();
    }

    public void in(Node head, List<Node> list) {
        if (head == null) {
            return;
        }
        in(head.left, list);
        list.add(head);
        in(head.right, list);
    }

    public static class Info {
        public int max;
        public int min;
        public int allSize;
        public int maxSize;

        public Info(int max, int min, int allSize, int maxSize) {
            this.max = max;
            this.min = min;
            this.allSize = allSize;
            this.maxSize = maxSize;
        }
    }

    public Info process(Node head) {
        if (head == null) {
            return null;
        }
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);
        int min = head.value;
        int max = head.value;
        int allSize = 1;
        int maxSize = 0;
        if (leftInfo != null) {
            allSize += leftInfo.allSize;
            min = Math.min(min, leftInfo.min);
            max = Math.max(max, leftInfo.max);
        }
        if (rightInfo != null) {
            allSize += rightInfo.allSize;
            min = Math.min(min, rightInfo.min);
            max = Math.max(max, rightInfo.max);
        }
        int p1 = -1;
        if (leftInfo != null) {
            p1 = leftInfo.maxSize;
        }
        int p2 = -1;
        if (rightInfo != null) {
            p2 = rightInfo.maxSize;
        }
        int p3 = -1;
        boolean leftBST = leftInfo == null ? true : (leftInfo.allSize == leftInfo.maxSize);
        boolean rightBST = rightInfo == null ? true : (rightInfo.allSize == rightInfo.maxSize);
        if (leftBST && rightBST) {
            boolean leftLessThanX = leftInfo == null ? true : (leftInfo.max < head.value);
            boolean rightMoreThanX = rightInfo == null ? true : (rightInfo.min < head.value);
            if (leftLessThanX && rightMoreThanX) {
                int leftSize = leftInfo == null ? 0 : leftInfo.maxSize;
                int rightSize = rightInfo == null ? 0 : rightInfo.maxSize;
                p3 = leftSize + rightSize + 1;
            }
        }
        return new Info(max, min, allSize, Math.max(p1, Math.max(p2, p3)));
    }
}
